It is a known technology in which the pattern of input signals is recognized and the signal sequence that has been input is converted into a corresponding symbol string. For example, there are known technologies such as the technology for recognizing speech signals; the optical character recognition (OCR) technology in which characters are recognized from an image in which the characters are written; the technology for recognizing handwritten characters; and the technology for recognizing a gesture or sign language from an image. As a device for implementing such technologies, a decoder is known that searches a digraph which is formed by adding output symbols to a weighted finite state automaton (i.e., searches a weighted finite state transducer (WFST)).
In the case of performing speech recognition using a WFST-searching decoder, the hidden Markov model (HMM) needs to be modified to be available for use in such a decoder. For example, in order to make the HMM available for use in a WFST-searching decoder, input symbols of a WFST are assigned with an acoustic score function identifier that identifies a function for calculating an acoustic score.
However, if the input symbols are assigned with a score function identifier, in order to correctly deal with the self-transitions of the HMM, it is also necessary to set a limitation on the WFST that transitions assigned with only one type of input symbols are incoming to or outgoing from a single state. For that reason, the WFST to be searched using such a decoder has a large number of states and a large number of transitions, which leads to the need of having a large memory capacity.